#include <iostream>
#include <limits.h>
#include <cassert>

using namespace std;
/*
 * 题目：输入2个int型整数，它们进行除法计算并返回商，
 * 要求不得使用乘号'*'、除号'/'及求余符号'%'。
 * 当发生溢出时，返回最大的整数值。假设除数不为0。
 * 例如，输入15和2，输出15/2的结果，即7。
 *
 */
/*
 * 一种更简洁的编程模式:
 *      1. 编写符合一般逻辑的输入格式正确算法处理步骤, core_fuction();
 *      2. 编写含有输入数据异常处理的程序(function()), 且内嵌core_function.
 *
 *
 */


// divident 被除数  divisor 除数
/*
 * 描述
 *      正确输入数据的core_function(), 即divideCore()
 * 参数
 *      dividend 被除数
 *      divisor 除数
 * 返回值
 *      商
 * 思路
 *      1.利用左移位运算, 首先计算出含有多少个divisor的2的幂次个, 即quotient;
 *      2.然后被除数dividend= dividend-divisor*quuotiend;
 *      3.循环上述步骤.
 *
 *
 *
 */

// 只处理负整数, 且dividend > divisor
int divideCore(int dividend, int divisor)
{
    int result = 0;     // 结果
    int value = 0;      // 每次需要减去的除数的最大倍数
    int quotient = 1;   // 记录每次循环需要多少个divisor
    while(dividend <= divisor)
    {
        value = divisor;
        quotient = 1;
        // 被除数 <= divisor * 2^quotient, 求出最大的quotient
        // 此处 0xc0000000 是 INT_MIN的一半, 意味着value不能再小了(注意此处使用负数(补码)讨论)
        // value >=0xc0000000这个条件用于保证dividend <= (value << 2)成立,
        // 如果发生溢出, 则会出现问题, 此时value由负数变为正数, 很显然有问题
        while(value >=0xc0000000 && dividend <= (value << 2))
        {
            value <<= 2;
            quotient <<= 2;
        }
        result += quotient;
        dividend -= value;
    }
    return result;
}

int divide(int divident, int divisor)
{
    //0x80000000为最小得int型整数，-2^31
    if (divident == 0x80000000 && divisor == -1)
    {
        // 实际这里运算是错误的
        return INT32_MAX;
    }
    int negative = 2;
    if (divident > 0)
    {
        negative--;
        divident = -divident;
    }
    if (divisor > 0)
    {
        negative--;
        divisor = -divisor;
    }

    int result = divideCore(divident, divisor);
    return negative == 1 ? -result : result;
}

/*
 * 总结:
 *      数值问题, 如果是补码, 一定要转成负数处理, 因为负数的补码范围要更大,
 *      如果不转成负数处理, 会发生值溢出
 *
 *
 *
 */

int main()
{
    ::printf("0xc0000000 = %d\n",0xc0000000);
    ::printf("INT_MIN = %d\n", INT_MIN);
    assert(INT_MIN == 0xc0000000);
    return 0;
}